20240606 2938 - Medium - Array

2938. Separate Black and White Balls

Original Solution, simulate

class Solution:
    def minimumSteps(self, s: str) -> int:
        sl = list(s)
        ans = 0
        j = len(s) - 1
        while j > 0:
            i = j
            while j >= 0 and sl[j] == "0": # edge case "00"
                while i > 0 and sl[i] == "0":
                    i -= 1
                if sl[i] == "1":
                    ans += j - i
                    sl[i], sl[j] = sl[j], sl[i]
                j -= 1
            j -= 1
        return ans

Solution from 0x3f

Idea:

• 乘法原理是组合计数的基本计数原理。简而言之，"若有 a 种方法做某事， b 种方法做另一事，则合共有 aXb 种方法做此两件事。
• Every "0" needs to swap with all the "1" to its left

class Solution:
    def minimumSteps(self, s: str) -> int:
        ans = 0
        cnt = 0
        for c in s:
            if c == "1":
                cnt += 1
            else:
                ans += cnt
        return ans